This invention relates to the modeling and rendering of 3D graphic objects.
Modeling and rendering of 3D graphic objects are used, for example, to generate 3D virtual scenes on the display screen of a computer system. The surface topology of a 3D object may be modeled as a set of polygons of appropriate sizes and shapes joined at their edges. The set of polygons defining the 3D object is referred to as the "model" or "mesh" for the 3D object. If the 3D object is to be displayed in wire-frame form, only the edge lines that form the polygons in the mesh are rendered, thus generating a skeleton-like image of the object. For example, the model of an X-29 aircraft shown in FIG. 2a consists of 957 unfilled polygons joined together at their edges to form a wire-frame representation of the aircraft. A more realistic rendering of the 3D object may be achieved by filling in the polygons with various colors as appropriate, for example, as shown in FIG. 2b, by taking into account lighting, texture and surface properties of the object under consideration.
A complex or detailed 3D object may be composed of several thousand or more polygons. Because each polygon takes a finite amount of time for the computer to draw, an object being modeled by a large number of polygons takes proportionately longer to render. Various algorithmic techniques have been suggested in the art for reducing the number of polygons in a 3D model, such as those described by Jarek R. Rossignac and Paul Borrel in "Multi-Resolution 3D Approximations for Rendering Complex Scenes," IBM Research Report (1992), and by William J. Schroeder, Jonathon A. Zarge and William E. Lorensen in "Decimation of Triangle Meshes," Computer Graphics, Vol. 26, No. 2, pp. 65-70, July 1992. However, although reducing the number of polygons in a 3D model decreases the amount of time it takes the computer to render the 3D object, the quality of the resultant image also is reduced. Consequently, in modeling 3D objects, a developer strives to find the optimal balance between image quality and rendering time.
One technique for optimizing the number of polygons in a 3D object involves the creation and use of multiple levels-of-detail ("LOD") for the 3D object. Multiple versions of the same 3D object are created such that each version has a successively lower polygon count (and thus a lower level-of-detail) and such that each version is associated with a different viewing range. FIGS. 3a shows a high polygon count LOD for an airplane and FIG. 3b shows a LOD for the same airplane having a somewhat lower polygon count. When the airplane is to be rendered at a point relatively close to the viewer's eye, a high polygon count (equivalently, a high LOD) version of the object such as that in FIG. 3a is used, thus providing the viewer with greater detail for the object.
As the 3D object moves farther from the viewer's eye, the viewer requires, and expects to see, fewer details of the 3D object. Accordingly, a lower polygon count version of the object (as shown in FIG. 3b) may used in rendering the object, thus increasing system performance proportionately to the degree by which the polygon count was reduced.
Ideally, the various versions of the 3D object, and the associated viewing ranges at which they become active, should be crafted such that the attendant loss of detail as the 3D object moves farther from the eye is inconsequential to the viewer. In this manner, system performance may be increased without unduly degrading image quality. In practice, constructing an appropriate set of LOD's for a model can be a painstaking and difficult task for model authors. This further motivates the need for improved polygon reduction tools.
What is needed is an effective methodology for reducing polygon count in 3D object models without resulting in unpredictable degradation in image quality. The methodology should be effective whether or not multiple LOD versions of the model are being created.